package com.yun.algorithmproblem.leetcode;

import java.util.HashMap;

public class Leetcode2661 {
    /*
        思路：哈希表
     */
    public int firstCompleteIndex1(int[] arr, int[][] mat) {
        int m=mat.length;
        int n=mat[0].length;
        HashMap<Integer,int[]> hm=new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                hm.put(mat[i][j],new int[]{i,j});
            }
        }
        int[] rowCnt=new int[m];
        int[] colCnt=new int[n];
        for (int i = 0; i < arr.length; i++) {
            int[] val=hm.get(arr[i]);
            rowCnt[val[0]]++;
            if(rowCnt[val[0]]==n){
                return i;
            }
            colCnt[val[1]]++;
            if(colCnt[val[1]]==m){
                return i;
            }
        }
        return -1;
    }

    /*
        思路：使用一维数组存储二维数组
        1.一维数组的索引为二维数组存储的值
        2.一维数组的值为二维数组的行索引*行长度+列索引
     */
    public int firstCompleteIndex(int[] arr, int[][] mat){
        int m=mat.length,n=mat[0].length;
        int cnts=m*n;
        int[] map=new int[cnts+1],rows=new int[m],cols=new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int cur=mat[i][j];
                map[cur]=i*n+j;
            }
        }
        for (int i = 0; i < cnts; i++) {
            int cur=arr[i];
            int pos=map[cur];
            int x=pos/n,y=pos%n;
            rows[x]++;
            cols[y]++;
            if(rows[x]==m||cols[y]==n){
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr={1,3,4,2};
        int[][] mat={{1,4},{2,3}};
        int res=new Leetcode2661().firstCompleteIndex(arr,mat);
        System.out.println(res);
    }
}
